In many communication applications, a network element queues and processes data packets originating from different sources. Often, multiple packet sources compete with one another for access to a common resource associated with the network element, such as for bandwidth on a common output port. Several methods are known in the art for scheduling packets that compete for a common resource. For example, some scheduling methods use a Round Robin (RR) process, in which the packet sources are served in a cyclic order. In each RR round, each of the packet sources is served if it is eligible. When served, each source is permitted to send one packet.
Other methods use Deficit Round Robin (DRR) scheduling, which defines a traffic ratio among the different packet sources. By defining the traffic ratio, also referred to as a quantum value, some sources are allowed to consume more resources than others. DRR is described, for example, by Shreedhar and Varghese in “Efficient Fair Queuing Using Deficit Round Robin,” Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Aug. 28-Sep. 1, 1995, Cambridge, Mass., pages 231-242, which is incorporated herein by reference.
In some applications, packet sources are queued and scheduled in accordance with a scheduling hierarchy. For example, U.S. Patent Application Publication 2005/0152374 A1, whose disclosure is incorporated herein by reference, describes methods for scheduling of items in a hierarchy of schedules. The methods include propagation of minimum guaranteed scheduling rates among scheduling layers in a hierarchical schedule.
The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which: